翻訳と辞書 Words near each other ・ Graphic Communication Group Limited ・ Graphic Communications Conference ・ Graphic design ・ Graphic design occupations ・ Graphic designer ・ Graphic Era Hill University ・ Graphic Era University ・ Graphic Exchange Magazine ・ Graphic facilitation ・ Graphic Imaging Technology ・ Graphic kit ・ Graphic matroid ・ Graph (mathematics) ・ Graph algebra ・ Graph algebra (social sciences) ・ GRAph ALigner (GRAAL) ・ Graph amalgamation ・ Graph automorphism ・ Graph bandwidth ・ Graph C*-algebra ・ Graph canonization ・ Graph center ・ Graph coloring ・ Graph coloring game ・ Graph continuous function ・ Graph cut ・ Graph cuts in computer vision ・ Graph database ・ Graph drawing ・ Graph dynamical system Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク GRAph ALigner (GRAAL) ： ウィキペディア英語版 GRAph ALigner (GRAAL) GRAaph ALigner (GRAAL)〔Oleksii Kuchaiev, Tijana Milenković, Vesna Memisević, Wayne Hayes, and Nataša Pržulj, Topological network alignment uncovers biological function and phylogeny, Journal of the Royal Society Interface 2010, to appear.〕 is an algorithm for global network alignment that is based solely on network topology. It aligns two networks $G$ and $H$ by producing an alignment that consists of a set of ordered pairs $(x,\; y)$, where $x$ is a node in $G$ and $y$ is a node in $H$. GRAAL matches pairs of nodes originating in different networks based on their graphlet degree signature similarities,〔Tijana Milenkovic and Nataša Pržulj, Uncovering Biological Network Function via Graphlet Degree Signatures, Cancer Informatics 2008, 6:257–273.〕 where a higher similarity between two nodes corresponds to a higher topological similarity between their extended neighborhoods (out to distance 4). GRAAL produces global alignments, i.e., it aligns each node in the smaller network to exactly one node in the larger network. The matching proceeds using a technique analogous to the "seed and extend" approach of the popular BLAST algorithm for sequence alignment: it first chooses a single "seed" pair of nodes (one node from each network) with high graphlet degree signature similarity. It then expands the alignment radially outward around the seed as far as practical using a greedy algorithm (see (et al., 2010 )〔 for details). ==Method== When aligning two graphs $G(V,E)\backslash !$ and $H(U,F)$, GRAAL first computes costs of aligning each node $v$ in G with each node $u$ in $H$. The cost of aligning two nodes takes into account the graphlet degree signature similarity〔 between them, modified to reduce the cost as the degrees of both nodes increase, since higher degree nodes with similar signatures provide a tighter constraint than correspondingly similar low degree nodes. In this way, GRAAL align the densest parts of the networks first. Let $deg(v)$ be the degree of a node $v$ in network $G$, let $max\_$ be the maximum degree of nodes in $G$, let $S(v,u)$ be the graphlet degree signature similarity of nodes $v$ and $u$, and let $\backslash alpha$ be a parameter in (1 ) that controls the contribution of the node signature similarity to the cost function (that is, $1-\backslash alpha$ is the parameter that controls the contribution of node degrees to the cost function), then the cost of aligning nodes $v$ and $u$ is computed as: $C(v,u)\; =\; 2-\; ((1-\backslash alpha)\backslash times\backslash frac+\backslash alpha\; \backslash times\; S(v,u))$. A cost of $0$ corresponds to a pair of topologically identical nodes $v$ and $u$, while a cost close to $2$ corresponds to a pair of topologically different nodes. GRAAL chooses as the initial seed a pair of nodes $(v,u)$, $v\backslash in\; V$ and $u\backslash in\; U$, that have the smallest cost. Ties are broken randomly. Once the seed is found, GRAAL builds "spheres" of all possible radii around nodes $v$ and $u$. A sphere of radius $r$ around node $v$ is the set of nodes $S\_(v,r)=\backslash$ that are at distance $r$ from $v$, where the distance $d(v,x)$ is the length of the shortest path from $v$ to $x$. Spheres of the same radius in two networks are then greedily aligned together by searching for the pairs $(v\text{'},u\text{'}):\; v\text{'}\backslash in\; S\_(v,r)$ and $u\text{'}\backslash in\; S\_(u,r)$ that are not already aligned and that can be aligned with the minimal cost. When all spheres around the seed $(v,u)$ have been aligned, some nodes in both networks may remain unaligned. For this reason, GRAAL repeats the same algorithm on a pair of networks $(G^p,H^p)$ for $p=1,2,$ and $3$, and searches for the new seed again, if necessary. Network $G^p$ is defined as a new network $G^p=(V,E^p)$ having the same set of nodes as $G$ and having $(v,x)\backslash in\; E^$ if and only if the distance between nodes $v$ and $x$ in $G$ is less than or equal to $p$, i.e., $d\_(v,x)\backslash leq\; p$. Note that $G^1=G$. Using $G^p$, $p\; >\; 1$, allows us to align a path of length $p$ in one network to a single edge in another network, which is analogous to allowing "insertions" or "deletions" in a sequence alignment. GRAAL stops when each node from $G$ is aligned to exactly one node in $H$. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「GRAph ALigner (GRAAL)」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.